// run: $exec < input
#include <iostream>
#include <cmath>

long long c, s;

long long gcd(long long x, long long y)
{
	return !y ? x : gcd(y, x % y);
}

long long polya()
{
	long long ret = 0;
	for (int i = 0; i < s; i++)
		ret += pow(c, gcd(s, i));

	if (s & 1) ret += s * pow(c, s / 2 + 1);
	else {
		ret += s / 2 * pow(c, s / 2);
		ret += s / 2 * pow(c, s / 2 + 1);
	}
	return ret / (2 * s);
}

int main()
{
	while (std::cin >> c >> s && (c || s))
		std::cout << polya() << '\n';
}

